package com.lw.leetcode.arr.b;

/**
 * arr
 * 1262. 可被三整除的最大和
 *
 * @Author liw
 * @Date 2021/9/11 19:21
 * @Version 1.0
 */
public class MaxSumDivThree {

    public static void main(String[] args) {
        MaxSumDivThree test = new MaxSumDivThree();

        //输出：18
        int[] arr = {3, 6, 5, 1, 8};

        //输出：12
//        int[] arr = {1,2,3,4,4};

        // 0
//        int[] arr = {4};

        //51
//        int[] arr = {8,5,4,9,2,9,10,6};

        int i = test.maxSumDivThree(arr);
        System.out.println(i);
    }

    public int maxSumDivThree(int[] nums) {
        int length = nums.length;
        int sum = 0;
        int a1 = 0;
        int a2 = 0;
        long m1 = Integer.MAX_VALUE;
        long m2 = Integer.MAX_VALUE;
        long n1 = Integer.MAX_VALUE;
        long n2 = Integer.MAX_VALUE;
        for (int i = 0; i < length; i++) {
            int v = nums[i];
            sum += v;
            int m = v % 3;
            if (m == 1) {
                a1++;
                if (v <= m1) {
                    m2 = m1;
                    m1 = v;
                } else if (v < m2) {
                    m2 = v;
                }
            } else if (m == 2) {
                a2++;
                if (v <= n1) {
                    n2 = n1;
                    n1 = v;
                } else if (v < n2) {
                    n2 = v;
                }
            }
        }
        a1 %= 3;
        a2 %= 3;
        if (a1 == a2) {
            return sum;
        } else if (a1 - a2 == -1 || a1 - a2 == 2) {
            return (int) (sum - Math.min(n1, m1 + m2));
        }
        return (int) (sum - Math.min(m1, n1 + n2));
    }

}
